#include "Graph.hpp"
#include <map>
#include <set>
#include <queue>
#include <list>

template <typename T>
auto createGraph()
{
    Graph<T> G(9);
    std::map<unsigned, std::vector<std::pair<size_t, T>>> edges;
    edges[1] = { {2, 2}, {5, 3} };
    edges[2] = { {1, 2}, {5, 5}, {4, 1} };
    edges[3] = { {4, 2}, {7, 3} };
    edges[4] = { {2, 1}, {3, 2}, {5, 2}, {6, 4}, {8, 5} };
    edges[5] = { {1, 3}, {2, 5}, {4, 2}, {8, 3} };
    edges[6] = { {4, 4}, {7, 4}, {8, 1} };
    edges[7] = { {3, 3}, {6, 4} };
    edges[8] = { {4, 5}, {5, 3}, {6, 1} };
    for (auto& i : edges)
        for (auto& j : i.second)
            G.addEdge(Edge<T>{ i.first, j.first, j.second });
    return G;
}

template <typename T>
struct Label {
    size_t vertexID;
    T distance;
    Label(size_t id, T d): vertexID(id), distance(d) {}
    inline bool operator<(const Label<T>& that) const {
        return distance < that.distance;
    }
    inline bool operator>(const Label<T>& that) const {
        return distance > that.distance;
    }
    inline bool operator()(const Label<T>& that) const {
        return operator>(that);
    }
};

template <typename T>
auto dijkstraSolution(const Graph<T>& G, size_t src, size_t dest) {
    std::priority_queue<
        Label<T>, 
        vector<Label<T>>, 
        std::greater<Label<T>>
    > heap;
    std::set<size_t> visited;
    vector<size_t> parent(G.vertices()); //记录每个点是从哪里来的
    vector<T> distance(G.vertices(), std::numeric_limits<T>::max());
    std::list<size_t> shortestPath;
    heap.emplace(src, 0);
    parent[src] = src;
    while (!heap.empty()) {
        auto currentVertex = heap.top();
        heap.pop();
        //到达终点退出条件
        if (currentVertex.vertexID == dest) {
            cout << "Destination " << currentVertex.vertexID
                 << " reached.\n";
            break;
        }

        if (visited.find(currentVertex.vertexID) == visited.end()) {
            cout << "Visiting vertex " << currentVertex.vertexID
                 << endl;
            for (const auto& e : G.edgesFromVertex(currentVertex.vertexID)) {
                auto neighborID = e.dest;
                //每个边的weight属性代表了它与对应顶点的距离
                auto newDistance = currentVertex.distance + e.weight;
                //如果新路线的净距离比该邻点的净距离小，则将邻点加入优先队列
                if (newDistance < distance[neighborID]) {
                    heap.emplace(neighborID, newDistance);
                    //将邻点的父节点设置为当前节点
                    parent[e.dest] = currentVertex.vertexID;
                    //将邻点的净距离修改为新路线的净距离
                    distance[e.dest] = newDistance;
                }
            }
            visited.insert(currentVertex.vertexID);
        }
    }
    auto currentVertexID = dest;
    while (currentVertexID != src) {
        shortestPath.insert(shortestPath.begin(), currentVertexID);
        currentVertexID = parent[currentVertexID];
    }
    shortestPath.insert(shortestPath.begin(), src);
    return shortestPath;
}

template <typename T>
void testDijkstra() {
    auto G = createGraph<T>();
    cout << "Graph:\n";
    cout << G << endl;
    auto shortestPath = dijkstraSolution<T>(G, 1, 6);
    cout << "The shortest path between 1 and 6 is:\n";
    for (const auto& v : shortestPath)
        cout << v << " -> ";
    cout << "finish" << endl;
}

int main(int argc, const char** argv) {
    using T = uint32_t;
    testDijkstra<T>();
    return 0;
}